public class BST {
    /**
     * 最优二叉搜索树
     * @author ShakeJ
     * @date 2024/1/1
     */
    /**
     * 给定n个关键字和它们被访问的概率，构造一棵二叉搜索树，使得搜索的平均代价最小。其中代价定义为搜索路径上各个结点的概率乘以其深度加1的总和。
     * @param p
     * @param n
     */
    public static void optimalBST(double[] p, int n) {
        double[][] cost = new double[n+2][n+1];
        int[][] root = new int[n+1][n+1];
        for (int i = 1; i <= n+1; i++) {
            cost[i][i-1] = 0;
        }
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n-len+1; i++) {
                int j = i+len-1;
                cost[i][j] = Double.MAX_VALUE;
                double sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += p[k];
                }
                for (int k = i; k <= j; k++) {
                    double temp = cost[i][k-1] + cost[k+1][j] + sum;
                    if (temp < cost[i][j]) {
                        cost[i][j] = temp;
                        root[i][j] = k;
                    }
                }
            }
        }
        System.out.printf("The minimum cost of optimal BST is %.2f\n", cost[1][n]);
        printTree(root, 1, n, 0);
    }

    public static void printTree(int[][] root, int i, int j, int level) {
        if (i <= j) {
            int r = root[i][j];
            System.out.print(indent(level));
            System.out.printf("Node %d\n", r);
            printTree(root, i, r-1, level+1);
            printTree(root, r+1, j, level+1);
        }
    }

    public static String indent(int level) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < level; i++) {
            sb.append("\t");
        }
        return sb.toString();
    }

    //我们使用了一个长度为6的概率数组p，其中p[0]为0，p[1]到p[5]分别表示关键字1到关键字5的访问概率

    public static void main(String[] args) {
        double[] p = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
        int n = p.length - 1;
        optimalBST(p, n);
    }

}
